#include "disjointset.h"

DisjointSet::DisjointSet(int fabricas, int clientes) {
	cantNodos = fabricas+clientes;
	tieneFabrica = new int[cantNodos];
	links = new int[cantNodos];
	ranks = new int[cantNodos];

	for(int i = 0; i < fabricas; i++) {
		tieneFabrica[i] = 1;
		links[i] = -1;
		ranks[i] = 0;
	}
	for(int i = fabricas; i < fabricas+clientes; i++) {
		tieneFabrica[i] = 0;
		links[i] = -1;
		ranks[i] = 0;
	}
}

DisjointSet::~DisjointSet() {
	delete[] tieneFabrica;
	delete[] links;
	delete[] ranks;
}

int DisjointSet::padre(int i) {
	/* devuelve el conjunto al que pertenece el elemento i */

	list<int> valores;

	while(links[i] != -1) {
		valores.push_back(i);
		i = links[i];
	}

	/* path-compression */
	for(list<int>::const_iterator it = valores.begin(); it != valores.end(); it++) {
		links[*it] = i;
	}

	return i;
}

bool DisjointSet::unir(int i, int j) {
	/* une conjuntos según el rank */

	if(i == j || (tieneFabrica[i] && tieneFabrica[j])) {
		return false;
	}

	if(ranks[i] > ranks[j]) {
		links[j] = i;
	} else {
		links[i] = j;
		if(ranks[i] == ranks[j])
			ranks[j] = ranks[i] + 1;
	}

	if (tieneFabrica[i]) {
		tieneFabrica[j] = 1;
	} else {
		tieneFabrica[i] = 1;
	}
	return true;
}

ostream& operator<<(ostream &os, const DisjointSet &ds) {
	os << "elemts: ";
	for(int i = 0; i < ds.cantNodos; i++)
		os << setw(4) << i;
	os << endl;

	os << "links:  ";
	for(int i = 0; i < ds.cantNodos; i++)
		os << setw(4) << ds.links[i];
	os << endl;

	os << "ranks:  ";
	for(int i = 0; i < ds.cantNodos; i++)
		os << setw(4) << ds.ranks[i];
	os << endl;

	return os;
}
